//
//  Problem230.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 230. 二叉搜索树中第K小的元素
 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

 示例 1：
     输入：root = [3,1,4,null,2], k = 1
     输出：1
 示例 2：
     输入：root = [5,3,6,2,4,null,null,1], k = 3
     输出：3
 提示：
     树中的节点数为 n 。
     1 <= k <= n <= 104
     0 <= Node.val <= 104
      

     进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
 */
@objcMembers class Problem230: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(1)
        root.left?.right = TreeNode(2)
        root.right = TreeNode(4)
//        print(kthSmallestDie(root, 1))
        
        
        let lroot = TreeNode(5)
        lroot.left = TreeNode(3)
        lroot.left?.left = TreeNode(2)
        lroot.left?.left?.left = TreeNode(1)
        lroot.left?.right = TreeNode(4)
        lroot.right = TreeNode(6)
//        print(kthSmallestDie(lroot, 3))
        
        let mroot = TreeNode(1)

        mroot.right = TreeNode(2)
        print(kthSmallestDie(mroot, 2))
    }
    
    /*
     二叉搜索树：左节点 < 根 < 右节点
     思路：将二叉搜索树转换成数组，这个数据就是排好的，获取k-1的下标即可
     
     使用递归的思路：
     缺陷：需要遍历所有的节点
     */
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var result: [Int] = []
        kthSmallestDi(root, &result)
        
        return result[k-1]
    }
    
    func kthSmallestDi(_ root: TreeNode?, _ result: inout [Int]) {
        if root == nil {
            return
        }
        kthSmallestDi(root?.left, &result)
        result.append(root!.val)
        kthSmallestDi(root?.right, &result)
    }
    
    /*
     迭代：
     不需要遍历所有节点，使用计数器，先获取最小值，取到一个值，让k--
     1: 创建一个数组：从根节点开始，依次记录左测的根节点
     2: 记录完成后，最后一个值就是最小值，最后第二个是他的根，然后在遍历他的右侧
     */
    func kthSmallestDie(_ root: TreeNode?, _ k: Int) -> Int {
        var nodes: [TreeNode] = []
        var tRoot = root
        while tRoot != nil {
            nodes.append(tRoot!)
            tRoot = tRoot?.left
        }
        
        var n = k
        while nodes.isEmpty == false {
            n -= 1
            let left = nodes.removeLast()
            if n == 0 {
                return left.val
            }
            var rightNode = left.right
            while rightNode != nil {
                nodes.append(rightNode!)
                rightNode = rightNode?.left
            }
            print(nodes.count)
        }
        
        return -1
    }
    
}
